class Solution {
    public boolean verifyPostorder(int[] postorder) {
        int root = Integer.MAX_VALUE;
        Stack<Integer> stack = new Stack<>();
        for(int i = postorder.length-1;i>=0;i--) {
            //跟root比的都是左子树,右子树都弹出去了
            if(postorder[i] > root) {
                return false;
            }
            //遍历到了左子树,开始弹出栈中根结点的右子树,直到弹空(此时栈的最后一个结点就是i的根),不可能在弹出的过程中有比左子树小的根节点(循环中的条件是为了找到左子树!),更新root,此时i指向的位置是左子树
            //把左子树的根节点放到栈里,接下来遍历左子树根节点的右子树
            while(!stack.isEmpty() && postorder[i] < stack.peek()) {
                root = stack.pop();
            }
            stack.push(postorder[i]);
        }
        return true;
    }
}